package put.cs.two.to.tsp.calculators.implementation.greedy;

import put.cs.two.to.tsp.calculators.base.AbstractTSPSolutionCalculator;
import put.cs.two.to.tsp.models.Edge;
import put.cs.two.to.tsp.models.NodeSet;
import put.cs.two.to.tsp.models.Point;
import put.cs.two.to.tsp.models.TSPEdgesSolution;
import put.cs.two.to.tsp.models.TSPSolution;

public class CycleExtensionCalculator extends AbstractTSPSolutionCalculator {

    @Override
    public TSPSolution solve(NodeSet inputNodes, int startingIndex) {
        try {
            tmpInputNodes = (NodeSet) inputNodes.clone();
        } catch (CloneNotSupportedException e) {
            return null;
        }

        TSPEdgesSolution solution = new TSPEdgesSolution();
        Point startingPoint = inputNodes.get(startingIndex);
        tmpInputNodes.setUsed(startingPoint);
        Point nearestPoint = getNearestPoint(startingPoint);
        tmpInputNodes.setUsed(nearestPoint);
        Edge firstEdge = new Edge(startingPoint, nearestPoint);
        solution.addEdge(firstEdge, 0);
        int cycleLength = 2;

        while (cycleLength < inputNodes.getDestinatedCycleLength()) {
            int minRelaxationCost = Integer.MAX_VALUE;
            Move bestMove = null;
            for (Edge edge : solution.edges()) {
                for (Point point : tmpInputNodes.getUnusedPoints()) {
                    int relaxationCost = computeRelaxationCost(edge, point);
                    if (relaxationCost < minRelaxationCost) {
                        minRelaxationCost = relaxationCost;
                        bestMove = new Move();
                        bestMove.edge = edge;
                        bestMove.p = point;
                    }
                }
            }
            solution.applyMove(bestMove.edge, bestMove.p);
            tmpInputNodes.setUsed(bestMove.p);
            cycleLength++;
        }

        return solution;
    }

    private int computeRelaxationCost(Edge edge, Point point) {
        Edge toPoint = new Edge(edge.getFromPoint(), point);
        Edge fromPoint = new Edge(point, edge.getToPoint());
        return toPoint.getLength() + fromPoint.getLength() - edge.getLength();
    }

    private class Move {
        Edge edge;

        Point p;
    }
}
